package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 118 杨辉三角
 * 数组/双指针
 给定一个非负整数numRows，生成「杨辉三角」的前numRows行。
 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

 示例 1:
 输入: numRows = 5
 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

 示例2:
 输入: numRows = 1
 输出: [[1]]

 提示:
 1 <= numRows <= 30
 */
public class PascalTriangle {
    public static void main(String[] args) {

    }

    //双指针，外层内层循环，纯数学解法，100/9
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0;i < numRows;i++) {
            List<Integer> ret = new ArrayList<>();
            for (int j = 0;j <= i;j++) {
                if (j == 0 || j == i) {
                    ret.add(1);
                } else {
                    ret.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
                }
            }
            res.add(ret);
        }
        return res;
    }
}
